package 每日一题;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.Map;

public class No781森林中的兔子 {

    /**
     * 森林中，每个兔子都有颜色。
     * 其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。
     * 我们将这些回答放在 answers 数组里。
     * 返回森林中兔子的最少数量。
     *
     * 示例:
     * 输入: answers = [1, 1, 2]
     * 输出: 5
     * 解释:
     * 两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
     * 之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
     * 设回答了 "2" 的兔子为蓝色。
     * 此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
     * 因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
     * 输入: answers = [10, 10, 10]
     * 输出: 11
     * 输入: answers = []
     * 输出: 0
     * 说明:
     * answers 的长度最大为1000。
     * answers[i] 是在 [0, 999] 范围内的整数。
     */

    public int numRabbits(int[] answers) {

        if(answers==null||answers.length<1){
            return 0;
        }

        Map<Integer,Integer> map=new HashMap<>();

        for (int answer : answers) {
            map.put(answer,map.getOrDefault(answer,0)+1);
        }

        int sum=0;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int no=entry.getKey();//兔子说有多少个和我一样
            int count=entry.getValue();//总共多少个兔子这么说

            if(no==0){
                sum+=count;
                continue;
            }

            if(count<=(no+1)){
                sum+=(no+1);
                continue;
            }

            //多了
            int merchant=count/(no+1);
            int remainder=count%(no+1);
            if(remainder!=0){
                sum+=(no+1);
            }
            sum+=(merchant*(no+1));

        }

        return sum;
    }

    public static void main(String[] args) {
        No781森林中的兔子 n=new No781森林中的兔子();
        int[] arr={10,10,10};
        int result = n.numRabbits(arr);
        System.out.println(result);
    }

}
